{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Total Hamming Distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: totalHammingDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #汉明距离总和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>两个整数的&nbsp;<a href=\"https://baike.baidu.com/item/%E6%B1%89%E6%98%8E%E8%B7%9D%E7%A6%BB/475174?fr=aladdin\">汉明距离</a> 指的是这两个数字的二进制数对应位不同的数量。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>nums</code>，请你计算并返回 <code>nums</code> 中任意两个数之间 <strong>汉明距离的总和</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,14,2]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>在二进制表示中，4 表示为 0100 ，14 表示为 1110 ，2表示为 0010 。（这样表示是为了体现后四位之间关系）\n",
    "所以答案为：\n",
    "HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,14,4]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li>给定输入的对应答案符合 <strong>32-bit</strong> 整数范围</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [total-hamming-distance](https://leetcode.cn/problems/total-hamming-distance/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [total-hamming-distance](https://leetcode.cn/problems/total-hamming-distance/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,14,2]', '[4,14,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        N = len(nums)\n",
    "        if N==0:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        max_ = max(nums)\n",
    "        mask=1\n",
    "        while max_:\n",
    "            k=0\n",
    "            for n in nums:\n",
    "                if n&mask!=0:\n",
    "                    k+=1\n",
    "            ans+=(N-k)*k\n",
    "            mask= mask<<1\n",
    "            max_= max_>>1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        d = {i : [0, 0] for i in range(30)}\n",
    "        for i in range(30):\n",
    "            for k in range(n):\n",
    "                d[i][nums[k] & 1] += 1\n",
    "                nums[k] >>= 1\n",
    "        for _, arr in d.items():\n",
    "            ans += arr[0] * arr[1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        d = {i : [0, 0] for i in range(32)}\n",
    "        for i in range(32):\n",
    "            for k in range(n):\n",
    "                d[i][nums[k] & 1] += 1\n",
    "                nums[k] >>= 1\n",
    "        for _, arr in d.items():\n",
    "            ans += arr[0] * arr[1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            if(num == 0):\n",
    "                cnt += 1\n",
    "        while(cnt < n):\n",
    "            ones, zeros = 0, 0\n",
    "            for i, num in enumerate(nums):\n",
    "                if(num % 2 == 0):\n",
    "                    zeros += 1\n",
    "                else:\n",
    "                    ones += 1\n",
    "                if(num > 0 and num // 2 == 0):\n",
    "                    cnt += 1\n",
    "                nums[i] = num // 2\n",
    "            result += ones*zeros\n",
    "        return result\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            if(num == 0):\n",
    "                cnt += 1\n",
    "        while(cnt < n):\n",
    "            ones, zeros = 0, 0\n",
    "            for i, num in enumerate(nums):\n",
    "                if(num % 2 == 0):\n",
    "                    zeros += 1\n",
    "                else:\n",
    "                    ones += 1\n",
    "                if(num > 0 and num // 2 == 0):\n",
    "                    cnt += 1\n",
    "                nums[i] = num // 2\n",
    "            result += ones*zeros\n",
    "        return result\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            if(num == 0):\n",
    "                cnt += 1\n",
    "        while(cnt < n):\n",
    "            ones, zeros = 0, 0\n",
    "            for i, num in enumerate(nums):\n",
    "                if(num % 2 == 0):\n",
    "                    zeros += 1\n",
    "                else:\n",
    "                    ones += 1\n",
    "                if(num > 0 and num // 2 == 0):\n",
    "                    cnt += 1\n",
    "                nums[i] = num // 2\n",
    "            # print(zeros, ones)\n",
    "            result += ones*zeros\n",
    "        return result\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(30):\n",
    "            c = sum(((val >> i) & 1) for val in nums)\n",
    "            ans += c * (n - c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        bit = 30\n",
    "        cnt = [0] * bit\n",
    "        for x in nums:\n",
    "            for i in range(bit):\n",
    "                if x >> i & 1:\n",
    "                    cnt[i] += 1\n",
    "        ans = 0\n",
    "        for x in cnt:\n",
    "            ans += x * (len(nums) - x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        n=len(nums)\n",
    "        nums.sort(reverse=True)\n",
    "        while nums[0]>0:\n",
    "            arr=[0,0]\n",
    "            for i in range(0,n):\n",
    "                v=nums[i]%2\n",
    "                nums[i]//=2\n",
    "                arr[v]+=1\n",
    "            res+=(arr[0]*arr[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        len_nums = len(nums)\n",
    "        m=[len_nums for i in range(32)]\n",
    "        for num in nums:\n",
    "            for i in range(32):\n",
    "                t = num&1\n",
    "                if t==1:\n",
    "                    m[i]-=1\n",
    "                num=num>>1\n",
    "                if num==0:\n",
    "                    # m[i+1:]=[x+1 for x in m[i+1:]]\n",
    "                    break\n",
    "        res=0\n",
    "        for mm in m:\n",
    "            res+=mm*(len_nums-mm)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        len_nums = len(nums)\n",
    "        m=[len_nums for i in range(30)]\n",
    "        for num in nums:\n",
    "            for i in range(30):\n",
    "                if num&1==1:\n",
    "                    m[i]-=1\n",
    "                num=num>>1\n",
    "                if num==0:\n",
    "                    # m[i+1:]=[x+1 for x in m[i+1:]]\n",
    "                    break\n",
    "        res=0\n",
    "        for mm in m:\n",
    "            res+=mm*(len_nums-mm)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        bit = 30\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(bit):\n",
    "            c = sum((x >> i & 1) for x in nums)\n",
    "            ans += c * (n - c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        count = [0] * 32\n",
    "        for num in nums:\n",
    "            for i in range(32):\n",
    "                count[i] += (num >> i) & 1\n",
    "        \n",
    "        return sum([x * (len(nums) - x) for x in count])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        d = [0] * 32\n",
    "        for num in nums:\n",
    "            k = 0\n",
    "            while num:\n",
    "                if num & 1:\n",
    "                    d[k] += 1\n",
    "                k += 1\n",
    "                num = num >> 1\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for b in d:\n",
    "            res += b * (n - b)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        count = [0] * 32\n",
    "        for num in nums:\n",
    "            i = 0\n",
    "            while num:\n",
    "                count[i] += num & 1\n",
    "                num >>= 1\n",
    "                i += 1\n",
    "        \n",
    "        return sum([x * (len(nums) - x) for x in count])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(30):\n",
    "            c = sum(((val >> i) & 1) for val in nums)\n",
    "            ans += c * (n - c)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(30):\n",
    "            c = sum(((n >> i) & 1) for n in nums)\n",
    "            ans += c * (n - c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        len_nums = len(nums)\n",
    "        m,n=[0 for i in range(32)],[0 for i in range(32)]\n",
    "        for num in nums:\n",
    "            for i in range(32):\n",
    "                t = num%2\n",
    "                if t==0: m[i]+=1\n",
    "                else: n[i]+=1\n",
    "                num=num>>1\n",
    "                if num==0:\n",
    "                    m[i+1:]=[x+1 for x in m[i+1:]]\n",
    "                    break\n",
    "        res=0\n",
    "        for mm,nn in zip(m,n):\n",
    "            res+=mm*nn\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(31):\n",
    "            c = sum(((val >> i) & 1) for val in nums)\n",
    "            ans += c * (n - c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        bit_cnt = [0 for i in range(32)]\n",
    "        for num in nums:\n",
    "            cur = 0\n",
    "            while num:\n",
    "                if num & 1:\n",
    "                    bit_cnt[cur] += 1\n",
    "                num >>= 1\n",
    "                cur += 1\n",
    "        \n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for cnt in bit_cnt:\n",
    "            ans += cnt * (n - cnt)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        bit = 30\n",
    "        cnt = [0] * bit\n",
    "        for x in nums:\n",
    "            for i in range(bit):\n",
    "                if x >> i & 1:\n",
    "                    cnt[i] += 1\n",
    "        ans = 0\n",
    "        for x in cnt:\n",
    "            ans += x * (len(nums) - x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(30):\n",
    "            c = 0\n",
    "            for num in nums:\n",
    "                c += (num >> i) & 1\n",
    "            res += c * (n - c)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(30):\n",
    "            c = sum(((val >> i) & 1) for val in nums)\n",
    "            ans += c * (n - c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            ones = 0\n",
    "            zeros = 0\n",
    "            for num in nums:\n",
    "                low_bit = num >> i & 1\n",
    "                if low_bit:\n",
    "                    ones += 1\n",
    "                else:\n",
    "                    zeros += 1\n",
    "            ans += ones * zeros\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\r\n",
    "        # def hammingDistance(x, y):\r\n",
    "        #     xor = x ^ y\r\n",
    "        #     distance = 0\r\n",
    "        #     while xor:\r\n",
    "        #         distance = distance + 1\r\n",
    "        #         xor = xor & (xor - 1)\r\n",
    "        #     return distance\r\n",
    "\r\n",
    "        # ans = 0\r\n",
    "        # n = len(nums)\r\n",
    "        # for i in range(n - 1):\r\n",
    "        #     for j in range(i + 1, n):\r\n",
    "        #         ans += hammingDistance(nums[i], nums[j])\r\n",
    "        # return(ans)\r\n",
    "\r\n",
    "        # 每次计算一位所有的数目，10^9二进制数是30位\r\n",
    "        res = 0\r\n",
    "        n = len(nums)\r\n",
    "        for i in range(30):\r\n",
    "            tmp = 0\r\n",
    "            for v in nums:\r\n",
    "                if (v >> i) & 1:\r\n",
    "                    tmp += 1\r\n",
    "            res += tmp * (n - tmp)\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        ones = [0] * 32\n",
    "        ans = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            for b in range(32):\n",
    "                if (1 << b) & n:\n",
    "                    ans += i - ones[b]\n",
    "                    ones[b] += 1\n",
    "                else:\n",
    "                    ans += ones[b]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "      n=len(nums)\n",
    "      ans=0\n",
    "      #分别计算每一个二进制位对答案的贡献\n",
    "      for i in range(32):\n",
    "          mask=1<<i\n",
    "          m=0\n",
    "          for num in nums:\n",
    "              m+=(num&mask)>0         #计算所有元素这一二进制位上1的个数\n",
    "          ans+=(n-m)*m                #(n-m)个0 和 m个1 构成异或对答案的贡献\n",
    "      return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            c0, c1 = 0, 0\n",
    "            for j in range(len(nums)):\n",
    "                if (nums[j] >> i) & 1 == 1:\n",
    "                    c1 += 1\n",
    "                else:\n",
    "                    c0 += 1\n",
    "            res += c0 * c1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        total_distance = 0\n",
    "\n",
    "        for bit in range(32):\n",
    "            count_ones = sum(((num >> bit) & 1) for num in nums)\n",
    "            count_zeros = n - count_ones\n",
    "            total_distance += count_ones * count_zeros\n",
    "\n",
    "        return total_distance\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range (30):\n",
    "            c=0\n",
    "            for jk in nums:\n",
    "                c+=(jk>>i)&1\n",
    "            ans+=c*(len(nums)-c)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        len_nums = len(nums)\n",
    "        m=[len_nums for i in range(32)]\n",
    "        for num in nums:\n",
    "            for i in range(32):\n",
    "                t = num&1\n",
    "                if t==1:\n",
    "                    m[i]-=1\n",
    "                num=num>>1\n",
    "                if num==0:\n",
    "                    # m[i+1:]=[x+1 for x in m[i+1:]]\n",
    "                    break\n",
    "        res=0\n",
    "        for mm in m:\n",
    "            res+=mm*(len_nums-mm)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        # 求汉明距离\n",
    "        # def hmDistance(x, y):\n",
    "        #     return bin(x^y).count(\"1\") # bin就是转为字符串\n",
    "        \n",
    "        # # 暴力----超时\n",
    "        # n = len(nums)\n",
    "        # res = 0\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i+1, n, 1):\n",
    "        #         d = hmDistance(nums[i], nums[j])\n",
    "        #         res += d\n",
    "        # return res\n",
    "\n",
    "\n",
    "        # 做成矩阵\n",
    "        # res = 0\n",
    "        # n = len(nums)\n",
    "        # matrix = [bin(nu)[2:].zfill(31) for nu in nums]\n",
    "        # print(matrix)\n",
    "        # # xy_matrix = zip(*matrix)\n",
    "        # # print(list(xy_matrix))\n",
    "        # for row  in zip(*matrix):\n",
    "        #     co = row.count(\"1\")\n",
    "        #     res += co*(n-co)\n",
    "        # return res\n",
    "\n",
    "\n",
    "        count_list = [0] * 31\n",
    "        ret, ln = 0, len(nums)\n",
    "        for num in nums:\n",
    "            for index, s in enumerate(bin(num)[2:][::-1]):\n",
    "                if s == '1':\n",
    "                    count_list[index] += 1\n",
    "        print(count_list)\n",
    "        for count in count_list:\n",
    "            ret += count * (ln - count)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        \n",
    "        for i in range(31):\n",
    "            c = 0\n",
    "            for a in nums:\n",
    "                c += (a >> i) & 1\n",
    "            \n",
    "            res += c * (n - c)\n",
    "            \n",
    "        return res \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef totalHammingDistance(self, nums):\n",
    "\t\ta = [[0, 0] for _ in range(32)]\n",
    "\t\tfor x in nums:\n",
    "\t\t\tfor i in range(len(a)):\n",
    "\t\t\t\ta[i][1 if (x & (1 << i)) else 0] += 1\n",
    "\t\treturn sum(x * y for x, y in a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        d = [0] * 32\n",
    "        for num in nums:\n",
    "            k = 0\n",
    "            while num:\n",
    "                if num & 1:\n",
    "                    d[k] += 1\n",
    "                k += 1\n",
    "                num = num >> 1\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for b in d:\n",
    "            res += b * (n - b)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        rc = [0]*32\n",
    "        for num in nums:\n",
    "            num_bin = bin(num)[-1:1:-1]\n",
    "            for i, bit in enumerate(num_bin):\n",
    "                if bit == '1': rc[31-i] += 1\n",
    "        \n",
    "        cnt = 0\n",
    "        for r in rc:\n",
    "            cnt += r * (len(nums) - r)\n",
    "\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(30):\n",
    "            c = sum(((val >> i) & 1) for val in nums)  # 第i位为1的个数\n",
    "            ans += c * (n - c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums):\n",
    "        count_list = [0] * 31\n",
    "        ret, ln = 0, len(nums)\n",
    "        for num in nums:\n",
    "            for index, s in enumerate(bin(num)[2:][::-1]):\n",
    "                if s == '1':\n",
    "                    count_list[index] += 1\n",
    "        for count in count_list:\n",
    "            ret += count * (ln - count)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        len_nums = len(nums)\n",
    "        m,n=[len_nums for i in range(32)],[0 for i in range(32)]\n",
    "        for num in nums:\n",
    "            for i in range(32):\n",
    "                t = num%2\n",
    "                if t==1:\n",
    "                    n[i]+=1\n",
    "                    m[i]-=1\n",
    "                num=num>>1\n",
    "                if num==0:\n",
    "                    # m[i+1:]=[x+1 for x in m[i+1:]]\n",
    "                    break\n",
    "        res=0\n",
    "        for mm,nn in zip(m,n):\n",
    "            res+=mm*nn\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        bit_count = {i: [0, 0] for i in range(32)}\n",
    "        for i in range(len(nums)):\n",
    "            index = 0\n",
    "            x = nums[i]\n",
    "            for j in range(32):\n",
    "                bit = x % 2\n",
    "                bit_count[index][bit] += 1\n",
    "                x = x >> 1\n",
    "                index += 1\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            res += (bit_count[i][0] * bit_count[i][1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(30):\n",
    "            c = sum(((val >> i) & 1) for val in nums)\n",
    "            ans += c * (n - c)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        # 逐位统计: 统计某一位上0和1的个数, 两者个数之和即为该位的汉明距离\n",
    "        # 10**9 < 2**30, (num >> i) & 1 可以取出 num 第 i 位的比特\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(32):\n",
    "            c = sum([(num >> i) & 1 for num in nums])\n",
    "            ans += c * (n - c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(31):\n",
    "            c = sum(((n >> i) & 1) for n in nums)\n",
    "            ans += c * (n - c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(30):\n",
    "            c = sum(((num >> i) & 1) for num in nums)\n",
    "            ans += c * (n-c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            c = sum(((n >> i) & 1) for n in nums)\n",
    "            ans += c * (n - c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        cnt = [0] * 31\n",
    "        ans = 0\n",
    "        for i in range(31): # 累积每个二进制位的计数\n",
    "            for num in nums:\n",
    "                if num >> i & 1:\n",
    "                    cnt[i] += 1\n",
    "            ans += cnt[i] * (len(nums) - cnt[i]) # 每个0分别与每个1组合，乘法原理\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for i in range(32):\n",
    "            mask = 1<<i\n",
    "            c = 0\n",
    "            for i in nums:\n",
    "                if mask&i>0:\n",
    "                    c+=1\n",
    "            \n",
    "            count+=(n-c)*c\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        len_nums = len(nums)\n",
    "        m,n=[len_nums for i in range(32)],[0 for i in range(32)]\n",
    "        for num in nums:\n",
    "            for i in range(32):\n",
    "                t = num%2\n",
    "                if t==1:\n",
    "                    n[i]+=1\n",
    "                    m[i]-=1\n",
    "                num=num>>1\n",
    "                if num==0:\n",
    "                    # m[i+1:]=[x+1 for x in m[i+1:]]\n",
    "                    break\n",
    "        res=0\n",
    "        for mm,nn in zip(m,n):\n",
    "            res+=mm*nn\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\r\n",
    "        # def hammingDistance(x, y):\r\n",
    "        #     xor = x ^ y\r\n",
    "        #     distance = 0\r\n",
    "        #     while xor:\r\n",
    "        #         distance = distance + 1\r\n",
    "        #         xor = xor & (xor - 1)\r\n",
    "        #     return distance\r\n",
    "\r\n",
    "        # ans = 0\r\n",
    "        # n = len(nums)\r\n",
    "        # for i in range(n - 1):\r\n",
    "        #     for j in range(i + 1, n):\r\n",
    "        #         ans += hammingDistance(nums[i], nums[j])\r\n",
    "        # return(ans)\r\n",
    "        res = 0\r\n",
    "        n = len(nums)\r\n",
    "        for i in range(30):\r\n",
    "            tmp = 0\r\n",
    "            for v in nums:\r\n",
    "                if (v >> i) & 1:\r\n",
    "                    tmp += 1\r\n",
    "            res += tmp * (n - tmp)\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        for j in range(32):\n",
    "            tmp=0\n",
    "            for i in range(len(nums)):\n",
    "                tmp+=(nums[i]>>j)&1\n",
    "            ans+=tmp*(n-tmp)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        ones = [0] * 32\n",
    "        for i, n in enumerate(nums):\n",
    "            for b in range(32):\n",
    "                if (1 << b) & n:\n",
    "                    ones[b] += 1\n",
    "\n",
    "        return sum((len(nums) - c) * c for c in ones)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        res=0\n",
    "        for i in range(30):\n",
    "            c=sum(((val >> i) & 1) for val in nums)\n",
    "            res+=c*(n-c)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(31):\n",
    "            c = sum(((n >> i) & 1) for n in nums)\n",
    "            ans += c * (n - c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        len_nums = len(nums)\n",
    "        m=[len_nums for i in range(32)]\n",
    "        for num in nums:\n",
    "            for i in range(32):\n",
    "                if num&1==1:\n",
    "                    m[i]-=1\n",
    "                num=num>>1\n",
    "                if num==0:\n",
    "                    # m[i+1:]=[x+1 for x in m[i+1:]]\n",
    "                    break\n",
    "        res=0\n",
    "        for mm in m:\n",
    "            res+=mm*(len_nums-mm)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(ceil(log(max(nums) + 1, 2))):\n",
    "            cnt = sum((x >> i) & 1 for x in nums)\n",
    "            ans += cnt * (n - cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        len_nums = len(nums)\n",
    "        m,n=[len_nums for i in range(32)],[0 for i in range(32)]\n",
    "        for num in nums:\n",
    "            for i in range(32):\n",
    "                t = num%2\n",
    "                if t==1:\n",
    "                    n[i]+=1\n",
    "                    m[i]-=1\n",
    "                num=num>>1\n",
    "                if num==0:\n",
    "                    # m[i+1:]=[x+1 for x in m[i+1:]]\n",
    "                    break\n",
    "        res=0\n",
    "        for mm,nn in zip(m,n):\n",
    "            res+=mm*nn\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(30):\n",
    "            c = sum(((val >> i) & 1) for val in nums)\n",
    "            ans += c * (n - c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(30):\n",
    "            c = sum(((val >> i) & 1) for val in nums)  # 第i位为1的个数\n",
    "            ans += c * (n - c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        count=[0 for _ in range(60)]\n",
    "        for i in range(len(nums)):\n",
    "            tmp=nums[i]\n",
    "            cal=0\n",
    "            while(tmp!=0):\n",
    "                count[cal]+=tmp&1\n",
    "                tmp=tmp>>1\n",
    "                cal+=1\n",
    "        ham=0\n",
    "        for i in count:\n",
    "            ham+=i*(len(nums)-i)\n",
    "        return ham"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\r\n",
    "        ret=0\r\n",
    "        N=len(nums)\r\n",
    "        for i in range(30):\r\n",
    "            cnt=sum([(n>>i) & 1 for n in nums])\r\n",
    "            ret+=cnt*(N-cnt)\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\r\n",
    "        # def hammingDistance(x, y):\r\n",
    "        #     xor = x ^ y\r\n",
    "        #     distance = 0\r\n",
    "        #     while xor:\r\n",
    "        #         distance = distance + 1\r\n",
    "        #         xor = xor & (xor - 1)\r\n",
    "        #     return distance\r\n",
    "\r\n",
    "        # ans = 0\r\n",
    "        # n = len(nums)\r\n",
    "        # for i in range(n - 1):\r\n",
    "        #     for j in range(i + 1, n):\r\n",
    "        #         ans += hammingDistance(nums[i], nums[j])\r\n",
    "        # return(ans)\r\n",
    "\r\n",
    "        # 每次计算一位所有的数目，10^9二进制数是30位\r\n",
    "        res = 0\r\n",
    "        n = len(nums)\r\n",
    "        for i in range(30):\r\n",
    "            tmp = 0\r\n",
    "            for v in nums:\r\n",
    "                if (v >> i) & 1:\r\n",
    "                    tmp += 1\r\n",
    "            res += tmp * (n - tmp)\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(30):\n",
    "            c = sum([((val >> i) & 1) for val in nums])\n",
    "            ans += c * (n - c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(32):\n",
    "            count = 0\n",
    "            for num in nums:\n",
    "                count += num >> i & 1\n",
    "            res += (n - count) *count\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        # 逐位统计: 统计某一位上0和1的个数, 两者个数之和即为该位的汉明距离\n",
    "        # 10**9 < 2**30, (num >> i) & 1 可以取出 num 第 i 位的比特\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(30):\n",
    "            c = sum([(num >> i) & 1 for num in nums])\n",
    "            ans += c * (n - c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(30):\n",
    "            c = sum(((val >> i) & 1) for val in nums)\n",
    "            ans += c * (n - c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalHammingDistance(self, nums: List[int]) -> int:\n",
    "        nums = [bin(i)[2:].zfill(32)[-32:] for i in nums]\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            c = collections.Counter(s[i] for s in nums)\n",
    "            res += c['0']*c['1']\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
